// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决

// 例题 2：
// 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
// 每条从根节点到叶节点的路径都代表一个数字：
// 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
// 计算从根节点到叶节点生成的 所有数字之和 。
// 叶节点 是指没有子节点的节点。
//
//        示例 1：
//
//
//        输入：root = [1,2,3]
//        输出：25
//        解释：
//        从根到叶子节点路径 1->2 代表数字 12
//        从根到叶子节点路径 1->3 代表数字 13
//        因此，数字总和 = 12 + 13 = 25
//        示例 2：
//
//
//        输入：root = [4,9,0,5,1]
//        输出：1026
//        解释：
//        从根到叶子节点路径 4->9->5 代表数字 495
//        从根到叶子节点路径 4->9->1 代表数字 491
//        从根到叶子节点路径 4->0 代表数字 40
//        因此，数字总和 = 495 + 491 + 40 = 1026
//
//
//        提示：
//
//        树中节点的数目在范围 [1, 1000] 内
//        0 <= Node.val <= 9
//        树的深度不超过 10

// 解题思路：
// 如果需要 dfs 干的事情太多，那就需要传参
// 找到相同子问题 - 每经过一层就需要拿到前面路径上所有的数字
// 函数头 - 需要传一个根节点，还需要传一个前面的路径值 dfs(root, preSum)
// 函数体 - 计算左子树的值，计算右子树的值，返回左右子树值的和
// 递归出口 - 叶子节点

public class SumNumbers {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int num){
        int preSum = num * 10 + root.val;
        if(root.left == null && root.right == null){
            return preSum;
        }
        int ret = 0;
        if(root.left != null) ret += dfs(root.left, preSum);
        if(root.right != null) ret += dfs(root.right, preSum);
        return ret;
    }
}
